“School of Biological Sciences”

Back to Papers Home
Back to Papers of School of Biological Sciences

Paper   IPM / Biological Sciences / 13214
School of Biological Sciences
  Title:   MC-Net: A Method For The Construction Of Phylogenetic Networks Based On The Monte-Carlo Method
  Author(s): 
1.  C. Eslahchi.
2.  M. Habibi.
3.  R. Hassanzadeh.
4.  E. Mottaghi.
  Status:   Published
  Journal: BMC Evolutionary Biology
  No.:  1
  Vol.:  10
  Year:  2010
  Pages:   254
  Supported by:  IPM
  Abstract:
Background A phylogenetic network is a generalization of phylogenetic trees that allows the representation of conflicting signals or alternative evolutionary histories in a single diagram. There are several methods for constructing these networks. Some of these methods are based on distances among taxa. In practice, the methods which are based on distance perform faster in comparison with other methods. The Neighbor-Net (N-Net) is a distance-based method. The N-Net produces a circular ordering from a distance matrix, then constructs a collection of weighted splits using circular ordering. The SplitsTree which is a program using these weighted splits makes a phylogenetic network. In general, finding an optimal circular ordering is an NP-hard problem. The N-Net is a heuristic algorithm to find the optimal circular ordering which is based on neighbor-joining algorithm.
Results In this paper, we present a heuristic algorithm to find an optimal circular ordering based on the Monte-Carlo method, called MC-Net algorithm. In order to show that MC-Net performs better than N-Net, we apply both algorithms on different data sets. Then we draw phylogenetic networks corresponding to outputs of these algorithms using SplitsTree and compare the results.
Conclusions We find that the circular ordering produced by the MC-Net is closer to optimal circular ordering than the N-Net. Furthermore, the networks corresponding to outputs of MC-Net made by SplitsTree are simpler than N-Net.

Download TeX format
back to top
scroll left or right